Système de congruences - Corrigé

Énoncé

On cherche à résoudre le système  \((S) \colon \left\lbrace \begin{array}{l}x \equiv 6 \ [13] \\ x \equiv 7 \ [19] \end{array} \right.\) .

1. Montrer que résoudre \((S)\) revient à résoudre l'équation \((E) \colon 13u+19v=1\) avec \((u;v) \in \mathbb{Z}^2\) .

2. Résoudre \((E)\) , puis en déduire les solutions de \((S)\) .

Solution

1. Soit \(x\) une solution de \((S)\) . Alors il existe \(k\) , \(k' \in \mathbb{Z}\) tels que \(x=6+13k\) et \(x=7+19k'\) .

On a donc \(\begin{align*}6+13k=7+19k'& \ \ \Longleftrightarrow \ \ 13k-19k'=7-6=1\ \ \Longleftrightarrow \ \ 13u+19v=1\end{align*}\)  avec \(u=k\) et \(v=-k'\) .

Réciproquement, soit \((u;v)\) une solution de \((E)\) . On pose \(x=7 \times 13u+6 \times 19v\) .

D'une part, on a \(x \equiv 6 \times 19v \ [13]\) , or \(19v=1-13u\) , donc \(x \equiv 6(1-13u) \equiv 6-6 \times 13u \equiv 6 \ [13]\) .

D'autre part, on a \(x \equiv 7 \times 13u \ [19]\) , or \(13u=1-19v\) , donc \(x \equiv 7(1-19v) \equiv 7-7 \times 19v \equiv 7 \ [19]\) .

Comme \(x \equiv 6 \ [13]\) et \(x \equiv 7 \ [19]\) , on en déduit que \(x\) est solution de \((S)\) .

Finalement, trouver une solution \(x\) de \((S)\) revient à trouver une solution \((u;v)\) de \((E)\) .

2.

• On applique l'algorithme d'Euclide pour  \(19\)  et  \(13\)  :
  \(\begin{align*}\renewcommand{\arraystretch}{1.2}\begin{array}{|c|c|c|c|}\hline a&b&q&r\\ \hline 19&13&1&6\\ \hline 13&6&2&1\\ \hline 6&1&6&0\\ \hline\end{array} \begin{array}{l}\ \\ \times (-2) \\ \times 1 \\ \ \end{array}\end{align*}\)  
  On a donc  \(\mathrm{PGCD}(13;19)=1\) , et comme \(1\) divise \(1\) , l'équation  \((E)\) admet des solutions dans \(\mathbb{Z}^2\) .
  
• En additionnant les lignes après avoir éliminé les restes intermédiaires, on obtient :
  \(\begin{align*}19 \times (-2)+13 \times 1=13 \times 1 \times (-2)+1& \ \ \Longleftrightarrow \ \ 13 \times 3+19 \times (-2)=1\end{align*}\)  
  donc \((u_0;v_0)=(3;-2)\) est une solution particulière de \((E)\) .
  
• Soit \((u;v)\) une solution de \((E)\) .
  On a  \(\begin{align*}13u+19v=13 \times 3+19 \times (-2)& \ \ \Longleftrightarrow \ \ 13(u-3)=19(-v-2)\end{align*}\)   
  donc \(13\) divise \(19(-v-2)\) .
  Or \(\mathrm{PGCD}(13;19)=1\) , donc d'après le théorème de Gauss, \(13\) divise \(-v-2\) , c'est-à-dire qu'il existe \(k \in \mathbb{Z}\) tel que  \(\begin{align*}-v-2=13k& \ \ \Longleftrightarrow \ \ v=-13k-2.\end{align*}\)  On a alors
  \(\begin{align*}13(u-3)=19(-v-2)& \ \ \Longleftrightarrow \ \ 13(u-3)=19 \times 13k\\& \ \ \Longleftrightarrow \ \ u-3=19k\\& \ \ \Longleftrightarrow \ \ u=19k+3.\end{align*}\)  
  Ainsi, les solutions de \((E)\) sont des couples de la forme  \((u;v)=(19k+3;-13k-2)\) avec \(k \in \mathbb{Z}\) .
  
• Réciproquement, soit \(k \in \mathbb{Z}\) quelconque et \((u;v)=(19k+3;-13k-2)\) .
  On a \(\begin{align*}13u+19v=13(19k+3)+19(-13k-2)=13 \times 3+19 \times (-2)=1\end{align*}\)   
  donc \((u;v)\) est solution de \((E)\) .
  
• En conclusion, les solutions de \((E)\) sont données par \(S=\left\lbrace(19k+3;-13k-2) \colon k \in \mathbb{Z} \right\rbrace\) .
  
• D'après la question 1, les solutions de \((S)\) sont donc les entiers \(x\) de la forme
  \(\begin{align*}x& = 7 \times 13(19k+3)+6 \times 19(-13k-2)\\& = 1\,729k+273-1\,482k-228\\& = 247k+45\end{align*}\)  
  avec \(k \in \mathbb{Z}\) .